package graph_viewer.structure;

import java.awt.Graphics;
import java.util.*;

import graph_viewer.canvas.*;
import graph_viewer.structure.clustering.*;
import graph_viewer.util.*;

/**
	@since 28/05/2004 no concrete implementation of do_cluster_action()
*/
public class Generic_Tree extends Tree {
	private	ArrayList		tree;	 // the collection of tree node
	private	Node		root;	
	
	//============================================================================
	// construtors
	//============================================================================
	public Generic_Tree(){
		tree	= new ArrayList();
	}
	
	public Generic_Tree( Node a_root ){
		this();
		set_root( a_root );	
	}
	
	// the nodes contain all the node, and their parent/children relationship.
	// the only node that has no parent is the root
	// be careful to call this constructor! because the root is still null.
	public Generic_Tree( ArrayList nodes ){
		set_tree( nodes );			
	}

	public Generic_Tree( Collection a_tree_node_collection ){
		this();
		//Debug.println( "Copy tree...", 3 );
		for ( Iterator iter	= a_tree_node_collection.iterator(); iter.hasNext() ; ){
			Node n = (Node) iter.next();
			//Debug.println( "Adding node " + n + " has children: " , 3 );
			this.tree.add( n );
			/*ArrayList children	= n.get_children();

			for ( Iterator _i = children.iterator(); _i.hasNext(); ){
				
				Node child	= (Node)_i.next();
				Debug.println( "\t\tChild: " + child, 3 );
			}
			add_node( new Node(n) );
			*/
		}
		//Debug.println( "Finishing Copy tree...", 3 );
	}

	public Generic_Tree( Tree gt ){
		this( new ArrayList( gt.get_tree() ) );		
	}
	//============================================================================
	// implemented methods
	//============================================================================	
	public void traverse( Command action ){
		////Debug.println( "Traversing:", 0 );

		for ( Iterator iter = tree.iterator(); iter.hasNext() ; ){
			Node tn	= (Node) iter.next();

			//Debug.println( "\t Generic_Tree.traverse:" +  tn, 2 );

			action.do_action( tn );
			//
		}
	}
	
	public Node search( String label ){
		// use the Graph.search()
		return search( tree, label );
	}

	public ArrayList find_nodes(){
		return get_tree();
	}

	public ArrayList find_edges(  ){
		ArrayList edges	= new ArrayList();		

		for ( Iterator _i = get_tree().iterator() ; _i.hasNext(); ){
			Node a_node	= (Node)_i.next();

			if (!is_leaf( a_node ) ){
				ArrayList children = a_node.get_children();
				
				for (Iterator iter=children.iterator(); iter.hasNext();){
					Node	child	= (Node)iter.next();
					String[] e		= new String[2];
					e[0]	= a_node.get_label();
					e[1]	= child.get_label();

					edges.add(e);
				}//end of for( iter.child )
			}//end of if( is_leaf )
		}//end of for ( iter._i)

		return edges;
	}
	
	// template hookers
	protected void draw_edges( final Graphics g, final Canvas_Metrics cm ){}
	protected void draw_nodes( final Graphics g, final Canvas_Metrics cm ){}
	protected void draw_clsuters( final Graphics g, final Canvas_Metrics cm ){}	

	public void do_cluster(  int thresholding, Graph_Canvas graph_canvas ){
		int i	= height();

		for ( ; i >=0 ; i--){
			// find all nodes of height i; 
			do_cluster_in_one_level( i, thresholding, find_edges() );
		}
	
	}
	// end of template hookers

	//==============end of Graph public methods============
	
	//a_psuedo_cluster should be added infront of it children, in order to get referrenced when copy to a new tree.
	//a_psuedo_cluster is added at the end of the tree_node, so when copy to a new tree, its children is add to node list first,
	//and can not find parent in the node list.
	private void reset_psuedo_clsuter_chilren( Node a_psuedo_cluster ){
		//Debug.println( "REsetting reset_psuedo_clsuter_chilren of :"+ a_psuedo_cluster, 3 );
		ArrayList children	= a_psuedo_cluster.get_children();

		for ( Iterator _i = children.iterator(); _i.hasNext(); ){
			
			Node child	= (Node)_i.next();
			//Debug.println( "Child: " + child, 3 );
			//Debug.println( "Current parent: " + child.get_parent().get_label(), 3 );
			child.set_parent( a_psuedo_cluster );
			//Debug.println( "Updated parent: " + child.get_parent().get_label(), 3 );
		}
	}

	//==============Tree public methods============
	// add a new tree node.
	public void add_node( Node a_node ){
		if ( is_empty() ){
			set_root( a_node );
			////Debug.println( "node " +  a_node + " added as root" , 0 );
		} else{
			tree.add( a_node );
			Node parent	= search( a_node.get_parent().get_label() );
			Node new_parent	= parent;
			new_parent.add_child( a_node );
			a_node.set_parent( new_parent );
			
			if ( a_node.get_is_psuedo() ){
				reset_psuedo_clsuter_chilren( a_node );
			}
		}
	}
	
	public void	delete_node( Node a_node ){
		Node the_node	= search( a_node.get_label() );
		Node parent		= search( a_node.get_parent().get_label());
		tree.remove( the_node );
		parent.delete_child( the_node );
	}

	public void empty(){
		tree.clear();
	}
	
	public void reset_tree( Tree a_tree ){

	}

	public Tree find_tree(){
		return this;
	} 
	
/**
	 * set set_DOI of all node
	 */
	//public void set_DOI( Node focus_node ){
	public void allocate_DOI( Node focus_node ){
		// different tree could use the node of the same label
		final Node the_focus	= search( focus_node.get_label() );
		traverse(
			new Command(){// this anoymous class command class calculate DOI and set it to the node.
				public void do_action( Node a_node ){
					
					//int doi	= calculate_DOI( a_node, the_focus );
					//a_node.set_DOI( doi );
				}
			}				
		);
	}
	
	/*public void reallocate_DOI(final int threshold_value ){
		// step 1:
		// reallocate DOI without consideration of the ancestor of a kept vertex.
		traverse(
			new Command(){
				public void do_action( Node a_node ){
					// DOI >= k, do change,
					// DOI < k, and demagnified, set DOI MIN_VALUE
					int current_DOI	= a_node.get_DOI();
					if ( ! (current_DOI < threshold_value) ){
						//do nothing but keep the current value.
					}else {// DOI < threshold value
						if ( a_node.is_demagnified() ){
							a_node.set_DOI( Graph.MIN_DOI );
						}else{
							a_node.set_DOI( Graph.MAX_DOI);
						}
					}
				}
			}				
		);
		
		// step 2:
		// all nodes has a new DOI
		// consideration of the ancestor of a kept vertex.
		// a magnified node's DOI is definitely not small er than threshold value because of step 1.
		// so, if a node' DOI is samller than DOI, then it should be rellocated.
		ArrayList magnified_and_ancesters	= get_magnified_and_ancesters();
		for (Iterator _i = magnified_and_ancesters.iterator(); _i.hasNext() ; ){
			Node a_node = (Node) _i.next();
			int DOI	= a_node.get_DOI();
			if ( DOI < threshold_value ){
				a_node.set_DOI( Graph.MAX_DOI);
			}			
		}

	}*/
	/* find the height of the tree */
	public int height(){
		int height	= 0;
		for ( Iterator iter = tree.iterator(); iter.hasNext(); ){
			Node node = (Node)iter.next();
			int depth	= depth( node );
			if ( depth > height ){
				height = depth;
			}
		}	

		return height;
	}
	
	public boolean is_leaf( Node a_node ){
		return a_node.get_children().size() == 0;
	}
	
	public boolean is_root( Node a_node ){
		return a_node == this.root;
	}

	public boolean is_empty(){
		return this.tree.size() == 0;
	}
	//==============Tree public methods============
	public ArrayList get_ancesters( Node tn ){
		ArrayList ancester = new ArrayList();
			
		if ( !is_root(tn) ){
			
			Node parent = tn ;

			while ( true ){
				parent	= get_parent( parent );				
				ancester.add( parent);

				if ( is_root(parent)){
					break;
				}
			}
		}

		return ancester;
	}
	
	public ArrayList find_descedants( Node tn ){
		ArrayList descedants = new ArrayList();

		for (Iterator _i = get_tree().iterator(); _i.hasNext(); ){
			Node node = (Node)_i.next();

			if ( is_ancestor(tn, node ) ){
				descedants.add( node );
			}
		}

		return descedants;
	}
	
	public Node get_parent(Node a_tree_node){
		return search(  a_tree_node.get_parent().get_label() );
	}
	//================= end of calculate_DOI helper====================
	
	
	public boolean is_ancestor( Node anc, Node desc ){
		//Debug.println( "is_ancestor: anc is: " + anc + ", desc is: " + desc, 5 );
		
		if ( anc.get_label().equals(desc.get_label() ) ){
			return false;
		}else if ( is_root( anc ) ){
			return true;
		}else if ( is_root( desc ) ){
			return false;
		}else{
			if ( is_child( anc, desc ) ){
				return true;
			}else{
				return is_ancestor( anc,  desc.get_parent()  );
			}
		}
	}
	
	// calculate_distance helper	
	private	boolean is_ancester_and_desc( Node a_node, Node another_node ){
		return is_ancestor( a_node, another_node ) || is_ancestor( another_node, a_node );
	}
	
	//is_ancestor helper
	private boolean is_child( Node anc, Node desc  ){
		return anc.get_children().contains( desc );
	}
	
	//============================================================================
	// getter & setter
	//============================================================================
	public ArrayList get_tree(){
		return this.tree;
	}	

	public Node get_root(){
		return this.root;
	}

	public void set_tree( ArrayList a_tree_node_list ){
		this.tree	 = a_tree_node_list;
	}

	public void set_root( Node a_node ){
		if ( !tree.contains(a_node) ){
			tree.add( a_node );
		}		
		
		this.root	 = a_node;
	}
	//============================================================================
	// private methods
	//============================================================================

	private void do_cluster_in_one_level( int height , int thresholding, ArrayList edges ){}


	// if ancester's DOI > k, do change; otherwise set as MAX_DOI
	private void set_DOI_of_magnified_and_ancesters( ArrayList magnified_ancesters, int threshold_value ){
		for ( Iterator _i = magnified_ancesters.iterator() ; _i.hasNext() ; ){
			Node ancester	 = (Node)_i.next();
			if ( ancester.get_DOI() < threshold_value ){
				ancester.set_DOI( Graph.MAX_DOI );
			}
		}
	}

	private ArrayList get_magnified_and_ancesters( ){
		//use HashSet to avoid repeat added
		HashSet magnified_and_ancesters = new HashSet();

		for ( Iterator iter = tree.iterator(); iter.hasNext() ; ){
			Node tn	= (Node) iter.next();
			if ( tn.is_magnified() ){
				ArrayList ancesters = get_ancesters( tn );
				magnified_and_ancesters.add( tn );
				magnified_and_ancesters.addAll( ancesters );
			}
		}

		return new ArrayList( magnified_and_ancesters );
	}

	/**
	 * find tree node's depth
	 */
	public int depth(Node a_tree_node){
		//Debug.println( "=====================", 2 );
		//Debug.println( "Find depth of " + a_tree_node, 2 );
		if ( is_root(a_tree_node) ){
			//Debug.println( " is_root(): " + a_tree_node, 2 );
			return 0;
		}else{
			//Debug.println( "parent of " + a_tree_node + " is " + a_tree_node.get_parent(), 2 );
			return 1 + depth( a_tree_node.get_parent() );
		}			
	}

	
	

	//============================================================================
	// package methods
	//============================================================================
	//calculate DOI
	int calculate_DOI( Node a_tree_node, Node focus){
		//Debug.println( "============Calcualte DOI=============", 2 );
		//Debug.println( "Calcualte DOI of: " + a_tree_node + ", focus is: " + focus, 2 );
		Node	nearest_common_ancestor
					= find_nearest_common_ancestor( a_tree_node, focus );	
		//Debug.println( "find_nearest_common_ancestor: " + nearest_common_ancestor, 2 );
		
		int
			distance_of_node_2_common_anceter	=  calculate_distance( a_tree_node, nearest_common_ancestor );
			//Debug.println( "distance_of_node_2_common_anceter: " + distance_of_node_2_common_anceter, 2 );

		int	
			distance_of_focus_2_common_anceter	=  calculate_distance( focus, nearest_common_ancestor );
			//Debug.println( "distance_of_focus_2_common_anceter: " + distance_of_focus_2_common_anceter, 2 );
		
		int	distance	= distance_of_focus_2_common_anceter + distance_of_node_2_common_anceter;
		
		int	LOD		= calculate_LOD( a_tree_node );
				
		int	DOI		=  LOD - distance;
		
		
		return DOI;
	}
	
	//================= calculate_DOI helper====================
	private Node find_nearest_common_ancestor( Node a_tree_node, Node another_tree_node){
		if ( is_root( a_tree_node ) || is_root( another_tree_node ) ){
			return get_root();
		}
		
		Node parent_of_a_tree_node	= search( a_tree_node.get_parent().get_label() );
		
		if ( a_tree_node.get_label() == another_tree_node.get_label() ){
			return a_tree_node;
		}else if ( is_ancestor( a_tree_node, another_tree_node)  ){
			return a_tree_node;
		}else if ( is_ancestor( another_tree_node, a_tree_node ) ){
			return another_tree_node;
		}else{
			return find_nearest_common_ancestor( parent_of_a_tree_node, another_tree_node );
		}
	}
	
	private int calculate_distance( Node a_node, Node focal_node ){
		//Debug.println( "calculate distance of " + a_node + " and " + focal_node, 2 );
		if ( a_node.get_label() == focal_node.get_label() ){
			return 0;
		}else if ( is_ancester_and_desc( a_node, focal_node) ){
			//Debug.println( " is_anc_desc", 2 );
			return Math.abs( depth( a_node ) - depth( focal_node ) );
		}else{
			return depth( a_node ) + depth( focal_node );
		}
	}
		
	private	int calculate_LOD( Node a_tree_node ){
		return depth( a_tree_node ) * (-1);
	}
	
	
}//:~
